home *** CD-ROM | disk | FTP | other *** search
/ Amiga Format CD 46 / Amiga Format CD46 (1999-10-20)(Future Publishing)(GB)[!][issue 1999-12].iso / -serious- / comms / www / urlx / ubi_bintree.h < prev    next >
C/C++ Source or Header  |  1999-09-06  |  35KB  |  737 lines
  1. #ifndef ubi_BinTree_H
  2. #define ubi_BinTree_H
  3. /* ========================================================================== **
  4.  *                              ubi_BinTree.h
  5.  *
  6.  *  Copyright (C) 1991-1997 by Christopher R. Hertel
  7.  *
  8.  *  Email:  crh@ubiqx.mn.org
  9.  * -------------------------------------------------------------------------- **
  10.  *
  11.  *  ubi_BinTree manages a simple binary tree.  Nothing fancy here.  No height
  12.  *  balancing, no restructuring.  Still, a good tool for creating short, low-
  13.  *  overhead sorted lists of things that need to be found in a hurry.
  14.  *
  15.  *  In addition, this module provides a good basis for creating other types
  16.  *  of binary tree handling modules.
  17.  *
  18.  * -------------------------------------------------------------------------- **
  19.  *
  20.  *  This library is free software; you can redistribute it and/or
  21.  *  modify it under the terms of the GNU Library General Public
  22.  *  License as published by the Free Software Foundation; either
  23.  *  version 2 of the License, or (at your option) any later version.
  24.  *
  25.  *  This library is distributed in the hope that it will be useful,
  26.  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  27.  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  28.  *  Library General Public License for more details.
  29.  *
  30.  *  You should have received a copy of the GNU Library General Public
  31.  *  License along with this library; if not, write to the Free
  32.  *  Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  33.  *
  34.  * -------------------------------------------------------------------------- **
  35.  *
  36.  * $Log: ubi_BinTree.h,v $
  37.  * Revision 2.4  1997/07/26 04:11:14  crh
  38.  * + Just to be annoying I changed ubi_TRUE and ubi_FALSE to ubi_trTRUE
  39.  *   and ubi_trFALSE.
  40.  * + There is now a type ubi_trBool to go with ubi_trTRUE and ubi_trFALSE.
  41.  * + There used to be something called "ubi_TypeDefs.h".  I got rid of it.
  42.  * + Added function ubi_btLeafNode().
  43.  *
  44.  * Revision 2.3  1997/06/03 05:15:27  crh
  45.  * Changed TRUE and FALSE to ubi_TRUE and ubi_FALSE to avoid conflicts.
  46.  * Also changed the interface to function InitTree().  See the comments
  47.  * for this function for more information.
  48.  *
  49.  * Revision 2.2  1995/10/03 22:00:40  CRH
  50.  * Ubisized!
  51.  * 
  52.  * Revision 2.1  95/03/09  23:43:46  CRH
  53.  * Added the ModuleID static string and function.  These modules are now
  54.  * self-identifying.
  55.  * 
  56.  * Revision 2.0  95/02/27  22:00:33  CRH
  57.  * Revision 2.0 of this program includes the following changes:
  58.  *
  59.  *     1)  A fix to a major typo in the RepaceNode() function.
  60.  *     2)  The addition of the static function Border().
  61.  *     3)  The addition of the public functions FirstOf() and LastOf(), which
  62.  *         use Border(). These functions are used with trees that allow
  63.  *         duplicate keys.
  64.  *     4)  A complete rewrite of the Locate() function.  Locate() now accepts
  65.  *         a "comparison" operator.
  66.  *     5)  Overall enhancements to both code and comments.
  67.  *
  68.  * I decided to give this a new major rev number because the interface has
  69.  * changed.  In particular, there are two new functions, and changes to the
  70.  * Locate() function.
  71.  *
  72.  * Revision 1.0  93/10/15  22:55:04  CRH
  73.  * With this revision, I have added a set of #define's that provide a single,
  74.  * standard API to all existing tree modules.  Until now, each of the three
  75.  * existing modules had a different function and typedef prefix, as follows:
  76.  *
  77.  *       Module        Prefix
  78.  *     ubi_BinTree     ubi_bt
  79.  *     ubi_AVLtree     ubi_avl
  80.  *     ubi_SplayTree   ubi_spt
  81.  *
  82.  * To further complicate matters, only those portions of the base module
  83.  * (ubi_BinTree) that were superceeded in the new module had the new names.
  84.  * For example, if you were using ubi_AVLtree, the AVL node structure was
  85.  * named "ubi_avlNode", but the root structure was still "ubi_btRoot".  Using
  86.  * SplayTree, the locate function was called "ubi_sptLocate", but the next
  87.  * and previous functions remained "ubi_btNext" and "ubi_btPrev".
  88.  *
  89.  * This was not too terrible if you were familiar with the modules and knew
  90.  * exactly which tree model you wanted to use.  If you wanted to be able to
  91.  * change modules (for speed comparisons, etc), things could get messy very
  92.  * quickly.
  93.  *
  94.  * So, I have added a set of defined names that get redefined in any of the
  95.  * descendant modules.  To use this standardized interface in your code,
  96.  * simply replace all occurances of "ubi_bt", "ubi_avl", and "ubi_spt" with
  97.  * "ubi_tr".  The "ubi_tr" names will resolve to the correct function or
  98.  * datatype names for the module that you are using.  Just remember to
  99.  * include the header for that module in your program file.  Because these
  100.  * names are handled by the preprocessor, there is no added run-time
  101.  * overhead.
  102.  *
  103.  * Note that the original names do still exist, and can be used if you wish
  104.  * to write code directly to a specific module.  This should probably only be
  105.  * done if you are planning to implement a new descendant type, such as
  106.  * red/black trees.  CRH
  107.  *
  108.  *  V0.0 - June, 1991   -  Written by Christopher R. Hertel (CRH).
  109.  *
  110.  * ========================================================================== **
  111.  */
  112.  
  113. /* -------------------------------------------------------------------------- **
  114.  * Macros and constants.
  115.  *
  116.  *  General purpose:
  117.  *    ubi_trTRUE  - Boolean TRUE.
  118.  *    ubi_trFALSE - Boolean FALSE.
  119.  *
  120.  *  Flags used in the tree header:
  121.  *    ubi_trOVERWRITE   - This flag indicates that an existing node may be
  122.  *                        overwritten by a new node with a matching key.
  123.  *    ubi_trDUPKEY      - This flag indicates that the tree allows duplicate
  124.  *                        keys.  If the tree does allow duplicates, the
  125.  *                        overwrite flag is ignored.
  126.  *
  127.  *  Node link array index constants:  (Each node has an array of three
  128.  *  pointers.  One to the left, one to the right, and one back to the
  129.  *  parent.)
  130.  *    LEFT    - Left child pointer.
  131.  *    PARENT  - Parent pointer.
  132.  *    RIGHT   - Right child pointer.
  133.  *    EQUAL   - Synonym for PARENT.
  134.  *
  135.  *  ubi_trCompOps:  These values are used in the ubi_trLocate() function.
  136.  *    ubi_trLT  - request the first instance of the greatest key less than
  137.  *                the search key.
  138.  *    ubi_trLE  - request the first instance of the greatest key that is less
  139.  *                than or equal to the search key.
  140.  *    ubi_trEQ  - request the first instance of key that is equal to the
  141.  *                search key.
  142.  *    ubi_trGE  - request the first instance of a key that is greater than
  143.  *                or equal to the search key.
  144.  *    ubi_trGT  - request the first instance of the first key that is greater
  145.  *                than the search key.
  146.  * -------------------------------------------------------------------------- **
  147.  */
  148.  
  149. #define ubi_trTRUE  0xFF
  150. #define ubi_trFALSE 0x00
  151.  
  152. #define ubi_trOVERWRITE 0x01        /* Turn on allow overwrite      */
  153. #define ubi_trDUPKEY    0x02        /* Turn on allow duplicate keys */
  154.  
  155. /* Pointer array index constants... */
  156. #define LEFT   0x00
  157. #define PARENT 0x01
  158. #define RIGHT  0x02
  159. #define EQUAL  PARENT
  160.  
  161. typedef enum {
  162.   ubi_trLT = 1,
  163.   ubi_trLE,
  164.   ubi_trEQ,
  165.   ubi_trGE,
  166.   ubi_trGT
  167.   } ubi_trCompOps;
  168.  
  169. /* -------------------------------------------------------------------------- **
  170.  * These three macros allow simple manipulation of pointer index values (LEFT,
  171.  * RIGHT, and PARENT).
  172.  *
  173.  *    Normalize() -  converts {LEFT, PARENT, RIGHT} into {-1, 0 ,1}.  C
  174.  *                   uses {negative, zero, positive} values to indicate
  175.  *                   {less than, equal to, greater than}.
  176.  *    AbNormal()  -  converts {negative, zero, positive} to {LEFT, PARENT,
  177.  *                   RIGHT} (opposite of Normalize()).  Note: C comparison
  178.  *                   functions, such as strcmp(), return {negative, zero,
  179.  *                   positive} values, which are not necessarily {-1, 0,
  180.  *                   1}.  This macro uses the the ubi_btSgn() function to
  181.  *                   compensate.
  182.  *    RevWay()    -  converts LEFT to RIGHT and RIGHT to LEFT.  PARENT (EQUAL)
  183.  *                   is left as is.
  184.  * -------------------------------------------------------------------------- **
  185.  */
  186. #define Normalize(W) ((char)((W)-EQUAL))
  187. #define AbNormal(W) ((char)( EQUAL+((char)ubi_btSgn( (W) )) ))
  188. #define RevWay(W) ((char)((W)==LEFT?RIGHT:((W)==RIGHT?LEFT:EQUAL)))
  189.  
  190. /* -------------------------------------------------------------------------- **
  191.  * These macros allow us to quickly read the values of the OVERWRITE and
  192.  * DUPlicate KEY bits of the tree root flags field.
  193.  * -------------------------------------------------------------------------- **
  194.  */
  195. #define Dups_OK(A) ((ubi_trDUPKEY & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
  196. #define Ovwt_OK(A) ((ubi_trOVERWRITE & ((A)->flags))?(ubi_trTRUE):(ubi_trFALSE))
  197.  
  198. /* -------------------------------------------------------------------------- **
  199.  * Typedefs...
  200.  * 
  201.  * ubi_trBool   - Your typcial true or false...
  202.  *
  203.  * Item Pointer:  The ubi_btItemPtr is a generic pointer. It is used to
  204.  *                indicate a key that is being searched for within the tree.
  205.  *                Searching occurs whenever the ubi_trFind(), ubi_trLocate(),
  206.  *                or ubi_trInsert() functions are called.
  207.  * -------------------------------------------------------------------------- **
  208.  */
  209.  
  210. typedef unsigned char ubi_trBool;
  211.  
  212. typedef void *ubi_btItemPtr;              /* A pointer to data within a node. */
  213.  
  214. /*  ------------------------------------------------------------------------- **
  215.  *  Binary Tree Node Structure:  This structure defines the basic elements of
  216.  *       the tree nodes.  In general you *SHOULD NOT PLAY WITH THESE FIELDS*!
  217.  *       But, of course, I have to put the structure into this header so that
  218.  *       you can use it as a building block.
  219.  *
  220.  *  The fields are as follows:
  221.  *    Link     -  an array of pointers.  These pointers are manipulated by
  222.  *                the BT routines.  The pointers indicate the left and right
  223.  *                child nodes and the parent node.  By keeping track of the
  224.  *                parent pointer, we avoid the need for recursive routines or
  225.  *                hand-tooled stacks to keep track of our path back to the
  226.  *                root.  The use of these pointers is subject to change without
  227.  *                notice.
  228.  *    gender   -  a one-byte field indicating whether the node is the RIGHT or
  229.  *                LEFT child of its parent.  If the node is the root of the
  230.  *                tree, gender will be PARENT.
  231.  *  ------------------------------------------------------------------------- **
  232.  */
  233. typedef struct ubi_btNodeStruct {
  234.   struct ubi_btNodeStruct *Link[ 3 ];
  235.   char                     gender;
  236.   } ubi_btNode;
  237.  
  238. typedef ubi_btNode *ubi_btNodePtr;     /* Pointer to an ubi_btNode structure. */
  239.  
  240. /*  ------------------------------------------------------------------------- **
  241.  * The next three typedefs define standard function types used by the binary
  242.  * tree management routines.  In particular:
  243.  *
  244.  *    ubi_btCompFunc    is a pointer to a comparison function.  Comparison
  245.  *                      functions are passed an ubi_btItemPtr and an
  246.  *                      ubi_btNodePtr.  They return a value that is (<0), 0,
  247.  *                      or (>0) to indicate that the Item is (respectively)
  248.  *                      "less than", "equal to", or "greater than" the Item
  249.  *                      contained within the node.  (See ubi_btInitTree()).
  250.  *    ubi_btActionRtn   is a pointer to a function that may be called for each
  251.  *                      node visited when performing a tree traversal (see
  252.  *                      ubi_btTraverse()).  The function will be passed two
  253.  *                      parameters: the first is a pointer to a node in the
  254.  *                      tree, the second is a generic pointer that may point to
  255.  *                      anything that you like.
  256.  *    ubi_btKillNodeRtn is a pointer to a function that will deallocate the
  257.  *                      memory used by a node (see ubi_btKillTree()).  Since
  258.  *                      memory management is left up to you, deallocation may
  259.  *                      mean anything that you want it to mean.  Just remember
  260.  *                      that the tree *will* be destroyed and that none of the
  261.  *                      node pointers will be valid any more.
  262.  *  ------------------------------------------------------------------------- **
  263.  */
  264.  
  265. typedef  int (*ubi_btCompFunc)( ubi_btItemPtr, ubi_btNodePtr );
  266.  
  267. typedef void (*ubi_btActionRtn)( ubi_btNodePtr, void * );
  268.  
  269. typedef void (*ubi_btKillNodeRtn)( ubi_btNodePtr );
  270.  
  271. /* -------------------------------------------------------------------------- **
  272.  * Tree Root Structure: This structure gives us a convenient handle for
  273.  *                      accessing whole AVL trees.  The fields are:
  274.  *    root  -  A pointer to the root node of the AVL tree.
  275.  *    count -  A count of the number of nodes stored in the tree.
  276.  *    cmp   -  A pointer to the comparison routine to be used when building or
  277.  *             searching the tree.
  278.  *    flags -  A set of bit flags.  Two flags are currently defined:
  279.  *
  280.  *       ubi_trOVERWRITE -  If set, this flag indicates that a new node should
  281.  *         (bit 0x01)       overwrite an old node if the two have identical
  282.  *                          keys (ie., the keys are equal).
  283.  *       ubi_trDUPKEY    -  If set, this flag indicates that the tree is
  284.  *         (bit 0x02)       allowed to contain nodes with duplicate keys.
  285.  *
  286.  *       NOTE: ubi_trInsert() tests ubi_trDUPKEY before ubi_trOVERWRITE.
  287.  *
  288.  * All of these values are set when you initialize the root structure by
  289.  * calling ubi_trInitTree().
  290.  * -------------------------------------------------------------------------- **
  291.  */
  292.  
  293. typedef struct {
  294.   ubi_btNodePtr  root;     /* A pointer to the root node of the tree       */
  295.   unsigned long  count;    /* A count of the number of nodes in the tree   */
  296.   ubi_btCompFunc cmp;      /* A pointer to the tree's comparison function  */
  297.   unsigned char  flags;    /* Overwrite Y|N, Duplicate keys Y|N...         */
  298.   } ubi_btRoot;
  299.  
  300. typedef ubi_btRoot *ubi_btRootPtr;  /* Pointer to an ubi_btRoot structure. */
  301.  
  302.  
  303. /* -------------------------------------------------------------------------- **
  304.  * Function Prototypes.
  305.  */
  306.  
  307. long ubi_btSgn( long x );
  308.   /* ------------------------------------------------------------------------ **
  309.    * Return the sign of x; {negative,zero,positive} ==> {-1, 0, 1}.
  310.    *
  311.    *  Input:  x - a signed long integer value.
  312.    *
  313.    *  Output: the "sign" of x, represented as follows:
  314.    *            -1 == negative
  315.    *             0 == zero (no sign)
  316.    *             1 == positive
  317.    *
  318.    * Note: This utility is provided in order to facilitate the conversion
  319.    *       of C comparison function return values into BinTree direction
  320.    *       values: {LEFT, PARENT, EQUAL}.  It is INCORPORATED into the
  321.    *       AbNormal() conversion macro!
  322.    *
  323.    * ------------------------------------------------------------------------ **
  324.    */
  325.  
  326. ubi_btNodePtr ubi_btInitNode( ubi_btNodePtr NodePtr );
  327.   /* ------------------------------------------------------------------------ **
  328.    * Initialize a tree node.
  329.    *
  330.    *  Input:   a pointer to a ubi_btNode structure to be initialized.
  331.    *  Output:  a pointer to the initialized ubi_btNode structure (ie. the
  332.    *           same as the input pointer).
  333.    * ------------------------------------------------------------------------ **
  334.    */
  335.  
  336. ubi_btRootPtr  ubi_btInitTree( ubi_btRootPtr   RootPtr,
  337.                                ubi_btCompFunc  CompFunc,
  338.                                unsigned char   Flags );
  339.   /* ------------------------------------------------------------------------ **
  340.    * Initialize the fields of a Tree Root header structure.
  341.    *  
  342.    *  Input:   RootPtr   - a pointer to an ubi_btRoot structure to be
  343.    *                       initialized.   
  344.    *           CompFunc  - a pointer to a comparison function that will be used
  345.    *                       whenever nodes in the tree must be compared against
  346.    *                       outside values.
  347.    *           Flags     - One bytes worth of flags.  Flags include
  348.    *                       ubi_trOVERWRITE and ubi_trDUPKEY.  See the header
  349.    *                       file for more info.
  350.    *
  351.    *  Output:  a pointer to the initialized ubi_btRoot structure (ie. the
  352.    *           same value as RootPtr).
  353.    * 
  354.    *  Note:    The interface to this function has changed from that of 
  355.    *           previous versions.  The <Flags> parameter replaces two      
  356.    *           boolean parameters that had the same basic effect.
  357.    * ------------------------------------------------------------------------ **
  358.    */
  359.  
  360. ubi_trBool ubi_btInsert( ubi_btRootPtr  RootPtr,
  361.                          ubi_btNodePtr  NewNode,
  362.                          ubi_btItemPtr  ItemPtr,
  363.                          ubi_btNodePtr *OldNode );
  364.   /* ------------------------------------------------------------------------ **
  365.    * This function uses a non-recursive algorithm to add a new element to the
  366.    * tree.
  367.    *
  368.    *  Input:   RootPtr  -  a pointer to the ubi_btRoot structure that indicates
  369.    *                       the root of the tree to which NewNode is to be added.
  370.    *           NewNode  -  a pointer to an ubi_btNode structure that is NOT
  371.    *                       part of any tree.
  372.    *           ItemPtr  -  A pointer to the sort key that is stored within
  373.    *                       *NewNode.  ItemPtr MUST point to information stored
  374.    *                       in *NewNode or an EXACT DUPLICATE.  The key data
  375.    *                       indicated by ItemPtr is used to place the new node
  376.    *                       into the tree.
  377.    *           OldNode  -  a pointer to an ubi_btNodePtr.  When searching
  378.    *                       the tree, a duplicate node may be found.  If
  379.    *                       duplicates are allowed, then the new node will
  380.    *                       be simply placed into the tree.  If duplicates
  381.    *                       are not allowed, however, then one of two things
  382.    *                       may happen.
  383.    *                       1) if overwritting *is not* allowed, this
  384.    *                          function will return FALSE (indicating that
  385.    *                          the new node could not be inserted), and
  386.    *                          *OldNode will point to the duplicate that is
  387.    *                          still in the tree.
  388.    *                       2) if overwritting *is* allowed, then this
  389.    *                          function will swap **OldNode for *NewNode.
  390.    *                          In this case, *OldNode will point to the node
  391.    *                          that was removed (thus allowing you to free
  392.    *                          the node).
  393.    *                          **  If you are using overwrite mode, ALWAYS  **
  394.    *                          ** check the return value of this parameter! **
  395.    *                 Note: You may pass NULL in this parameter, the
  396.    *                       function knows how to cope.  If you do this,
  397.    *                       however, there will be no way to return a
  398.    *                       pointer to an old (ie. replaced) node (which is
  399.    *                       a problem if you are using overwrite mode).
  400.    *
  401.    *  Output:  a boolean value indicating success or failure.  The function
  402.    *           will return FALSE if the node could not be added to the tree.
  403.    *           Such failure will only occur if duplicates are not allowed,
  404.    *           nodes cannot be overwritten, AND a duplicate key was found
  405.    *           within the tree.
  406.    * ------------------------------------------------------------------------ **
  407.    */
  408.  
  409. ubi_btNodePtr ubi_btRemove( ubi_btRootPtr RootPtr,
  410.                             ubi_btNodePtr DeadNode );
  411.   /* ------------------------------------------------------------------------ **
  412.    * This function removes the indicated node from the tree.
  413.    *
  414.    *  Input:   RootPtr  -  A pointer to the header of the tree that contains
  415.    *                       the node to be removed.
  416.    *           DeadNode -  A pointer to the node that will be removed.
  417.    *
  418.    *  Output:  This function returns a pointer to the node that was removed
  419.    *           from the tree (ie. the same as DeadNode).
  420.    *
  421.    *  Note:    The node MUST be in the tree indicated by RootPtr.  If not,
  422.    *           strange and evil things will happen to your trees.
  423.    * ------------------------------------------------------------------------ **
  424.    */
  425.  
  426. ubi_btNodePtr ubi_btLocate( ubi_btRootPtr RootPtr,
  427.                             ubi_btItemPtr FindMe,
  428.                             ubi_trCompOps CompOp );
  429.   /* ------------------------------------------------------------------------ **
  430.    * The purpose of ubi_btLocate() is to find a node or set of nodes given
  431.    * a target value and a "comparison operator".  The Locate() function is
  432.    * more flexible and (in the case of trees that may contain dupicate keys)
  433.    * more precise than the ubi_btFind() function.  The latter is faster,
  434.    * but it only searches for exact matches and, if the tree contains
  435.    * duplicates, Find() may return a pointer to any one of the duplicate-
  436.    * keyed records.
  437.    *
  438.    *  Input:
  439.    *     RootPtr  -  A pointer to the header of the tree to be searched.
  440.    *     FindMe   -  An ubi_btItemPtr that indicates the key for which to
  441.    *                 search.
  442.    *     CompOp   -  One of the following:
  443.    *                    CompOp     Return a pointer to the node with
  444.    *                    ------     ---------------------------------
  445.    *                   ubi_trLT - the last key value that is less
  446.    *                              than FindMe.
  447.    *                   ubi_trLE - the first key matching FindMe, or
  448.    *                              the last key that is less than
  449.    *                              FindMe.
  450.    *                   ubi_trEQ - the first key matching FindMe.
  451.    *                   ubi_trGE - the first key matching FindMe, or the
  452.    *                              first key greater than FindMe.
  453.    *                   ubi_trGT - the first key greater than FindMe.
  454.    *  Output:
  455.    *     A pointer to the node matching the criteria listed above under
  456.    *     CompOp, or NULL if no node matched the criteria.
  457.    *
  458.    *  Notes:
  459.    *     In the case of trees with duplicate keys, Locate() will behave as
  460.    *     follows:
  461.    *
  462.    *     Find:  3                       Find: 3
  463.    *     Keys:  1 2 2 2 3 3 3 3 3 4 4   Keys: 1 1 2 2 2 4 4 5 5 5 6
  464.    *                  ^ ^         ^                   ^ ^
  465.    *                 LT EQ        GT                 LE GE
  466.    *
  467.    *     That is, when returning a pointer to a node with a key that is LESS
  468.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  469.    *     LAST matching node.
  470.    *     When returning a pointer to a node with a key that is GREATER
  471.    *     THAN the target key (FindMe), Locate() will return a pointer to the
  472.    *     FIRST matching node.
  473.    *
  474.    *  See Also: ubi_btFind(), ubi_btFirstOf(), ubi_btLastOf().
  475.    * ------------------------------------------------------------------------ **
  476.    */
  477.  
  478. ubi_btNodePtr ubi_btFind( ubi_btRootPtr RootPtr,
  479.                           ubi_btItemPtr FindMe );
  480.   /* ------------------------------------------------------------------------ **
  481.    * This function performs a non-recursive search of a tree for any node
  482.    * matching a specific key.
  483.    *
  484.    *  Input:
  485.    *     RootPtr  -  a pointer to the header of the tree to be searched.
  486.    *     FindMe   -  a pointer to the key value for which to search.
  487.    *
  488.    *  Output:
  489.    *     A pointer to a node with a key that matches the key indicated by
  490.    *     FindMe, or NULL if no such node was found.
  491.    *
  492.    *  Note:   In a tree that allows duplicates, the pointer returned *might
  493.    *          not* point to the (sequentially) first occurance of the
  494.    *          desired key.  In such a tree, it may be more useful to use
  495.    *          ubi_btLocate().
  496.    * ------------------------------------------------------------------------ **
  497.    */
  498.  
  499. ubi_btNodePtr ubi_btNext( ubi_btNodePtr P );
  500.   /* ------------------------------------------------------------------------ **
  501.    * Given the node indicated by P, find the (sorted order) Next node in the
  502.    * tree.
  503.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  504.    *  Output:  A pointer to the "next" node in the tree, or NULL if P pointed
  505.    *           to the "last" node in the tree or was NULL.
  506.    * ------------------------------------------------------------------------ **
  507.    */
  508.  
  509. ubi_btNodePtr ubi_btPrev( ubi_btNodePtr P );
  510.   /* ------------------------------------------------------------------------ **
  511.    * Given the node indicated by P, find the (sorted order) Previous node in
  512.    * the tree.
  513.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  514.    *  Output:  A pointer to the "previous" node in the tree, or NULL if P
  515.    *           pointed to the "first" node in the tree or was NULL.
  516.    * ------------------------------------------------------------------------ **
  517.    */
  518.  
  519. ubi_btNodePtr ubi_btFirst( ubi_btNodePtr P );
  520.   /* ------------------------------------------------------------------------ **
  521.    * Given the node indicated by P, find the (sorted order) First node in the
  522.    * subtree of which *P is the root.
  523.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  524.    *  Output:  A pointer to the "first" node in a subtree that has *P as its
  525.    *           root.  This function will return NULL only if P is NULL.
  526.    *  Note:    In general, you will be passing in the value of the root field
  527.    *           of an ubi_btRoot structure.
  528.    * ------------------------------------------------------------------------ **
  529.    */
  530.  
  531. ubi_btNodePtr ubi_btLast( ubi_btNodePtr P );
  532.   /* ------------------------------------------------------------------------ **
  533.    * Given the node indicated by P, find the (sorted order) Last node in the
  534.    * subtree of which *P is the root.
  535.    *  Input:   P  -  a pointer to a node that exists in a binary tree.
  536.    *  Output:  A pointer to the "last" node in a subtree that has *P as its
  537.    *           root.  This function will return NULL only if P is NULL.
  538.    *  Note:    In general, you will be passing in the value of the root field
  539.    *           of an ubi_btRoot structure.
  540.    * ------------------------------------------------------------------------ **
  541.    */
  542.  
  543. ubi_btNodePtr ubi_btFirstOf( ubi_btRootPtr RootPtr,
  544.                              ubi_btItemPtr MatchMe,
  545.                              ubi_btNodePtr p );
  546.   /* ------------------------------------------------------------------------ **
  547.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  548.    * the tree, this function will return a pointer to the first (traversal
  549.    * order) node with the same key value.
  550.    *
  551.    *  Input:  RootPtr - A pointer to the root of the tree.
  552.    *          MatchMe - A pointer to the key value.  This should probably
  553.    *                    point to the key within node *p.
  554.    *          p       - A pointer to a node in the tree.
  555.    *  Output: A pointer to the first node in the set of nodes with keys
  556.    *          matching <FindMe>.
  557.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  558.    *          <FindMe>.  If not, this function will return NULL.
  559.    * ------------------------------------------------------------------------ **
  560.    */
  561.  
  562. ubi_btNodePtr ubi_btLastOf( ubi_btRootPtr RootPtr,
  563.                             ubi_btItemPtr MatchMe,
  564.                             ubi_btNodePtr p );
  565.   /* ------------------------------------------------------------------------ **
  566.    * Given a tree that a allows duplicate keys, and a pointer to a node in
  567.    * the tree, this function will return a pointer to the last (traversal
  568.    * order) node with the same key value.
  569.    *
  570.    *  Input:  RootPtr - A pointer to the root of the tree.
  571.    *          MatchMe - A pointer to the key value.  This should probably
  572.    *                    point to the key within node *p.
  573.    *          p       - A pointer to a node in the tree.
  574.    *  Output: A pointer to the last node in the set of nodes with keys
  575.    *          matching <FindMe>.
  576.    *  Notes:  Node *p MUST be in the set of nodes with keys matching
  577.    *          <FindMe>.  If not, this function will return NULL.
  578.    * ------------------------------------------------------------------------ **
  579.    */
  580.  
  581. ubi_trBool ubi_btTraverse( ubi_btRootPtr   RootPtr,
  582.                            ubi_btActionRtn EachNode,
  583.                            void           *UserData );
  584.   /* ------------------------------------------------------------------------ **
  585.    * Traverse a tree in sorted order (non-recursively).  At each node, call
  586.    * (*EachNode)(), passing a pointer to the current node, and UserData as the
  587.    * second parameter.
  588.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  589.    *                       the tree to be traversed.
  590.    *           EachNode -  a pointer to a function to be called at each node
  591.    *                       as the node is visited.
  592.    *           UserData -  a generic pointer that may point to anything that
  593.    *                       you choose.
  594.    *  Output:  A boolean value.  FALSE if the tree is empty, otherwise TRUE.
  595.    * ------------------------------------------------------------------------ **
  596.    */
  597.  
  598. ubi_trBool ubi_btKillTree( ubi_btRootPtr     RootPtr,
  599.                            ubi_btKillNodeRtn FreeNode );
  600.   /* ------------------------------------------------------------------------ **
  601.    * Delete an entire tree (non-recursively) and reinitialize the ubi_btRoot
  602.    * structure.  Note that this function will return FALSE if either parameter
  603.    * is NULL.
  604.    *
  605.    *  Input:   RootPtr  -  a pointer to an ubi_btRoot structure that indicates
  606.    *                       the root of the tree to delete.
  607.    *           FreeNode -  a function that will be called for each node in the
  608.    *                       tree to deallocate the memory used by the node.
  609.    *
  610.    *  Output:  A boolean value.  FALSE if either input parameter was NULL, else
  611.    *           TRUE.
  612.    *
  613.    * ------------------------------------------------------------------------ **
  614.    */
  615.  
  616. ubi_btNodePtr ubi_btLeafNode( ubi_btNodePtr leader );
  617.   /* ------------------------------------------------------------------------ **
  618.    * Returns a pointer to a leaf node.
  619.    *
  620.    *  Input:  leader  - Pointer to a node at which to start the descent.
  621.    *
  622.    *  Output: A pointer to a leaf node selected in a somewhat arbitrary
  623.    *          manner.
  624.    *
  625.    *  Notes:  I wrote this function because I was using splay trees as a
  626.    *          database cache.  The cache had a maximum size on it, and I
  627.    *          needed a way of choosing a node to sacrifice if the cache
  628.    *          became full.  In a splay tree, less recently accessed nodes
  629.    *          tend toward the bottom of the tree, meaning that leaf nodes
  630.    *          are good candidates for removal.  (I really can't think of
  631.    *          any other reason to use this function.)
  632.    *        + In a simple binary tree or an AVL tree, the most recently
  633.    *          added nodes tend to be nearer the bottom, making this a *bad*
  634.    *          way to choose which node to remove from the cache.
  635.    *        + Randomizing the traversal order is probably a good idea.  You
  636.    *          can improve the randomization of leaf node selection by passing
  637.    *          in pointers to nodes other than the root node each time.  A
  638.    *          pointer to any node in the tree will do.  Of course, if you
  639.    *          pass a pointer to a leaf node you'll get the same thing back.
  640.    *
  641.    * ------------------------------------------------------------------------ **
  642.    */
  643.  
  644.  
  645. int ubi_btModuleID( int size, char *list[] );
  646.   /* ------------------------------------------------------------------------ **
  647.    * Returns a set of strings that identify the module.
  648.    *
  649.    *  Input:  size  - The number of elements in the array <list>.
  650.    *          list  - An array of pointers of type (char *).  This array
  651.    *                  should, initially, be empty.  This function will fill
  652.    *                  in the array with pointers to strings.
  653.    *  Output: The number of elements of <list> that were used.  If this value
  654.    *          is less than <size>, the values of the remaining elements are
  655.    *          not guaranteed.
  656.    *
  657.    *  Notes:  Please keep in mind that the pointers returned indicate strings
  658.    *          stored in static memory.  Don't free() them, don't write over
  659.    *          them, etc.  Just read them.
  660.    * ------------------------------------------------------------------------ **
  661.    */
  662.  
  663. /* -------------------------------------------------------------------------- **
  664.  * Masquarade...
  665.  *
  666.  * This set of defines allows you to write programs that will use any of the
  667.  * implemented binary tree modules (currently BinTree, AVLtree, and SplayTree).
  668.  * Instead of using ubi_bt..., use ubi_tr..., and select the tree type by
  669.  * including the appropriate module header.
  670.  */
  671.  
  672. #define ubi_trItemPtr ubi_btItemPtr
  673.  
  674. #define ubi_trNode    ubi_btNode
  675. #define ubi_trNodePtr ubi_btNodePtr
  676.  
  677. #define ubi_trRoot    ubi_btRoot
  678. #define ubi_trRootPtr ubi_btRootPtr
  679.  
  680. #define ubi_trCompFunc    ubi_btCompFunc
  681. #define ubi_trActionRtn   ubi_btActionRtn
  682. #define ubi_trKillNodeRtn ubi_btKillNodeRtn
  683.  
  684. #define ubi_trSgn( x ) ubi_btSgn( x )
  685.  
  686. #define ubi_trInitNode( Np ) ubi_btInitNode( (ubi_btNodePtr)(Np) )
  687.  
  688. #define ubi_trInitTree( Rp, Cf, Fl ) \
  689.         ubi_btInitTree( (ubi_btRootPtr)(Rp), (ubi_btCompFunc)(Cf), (Fl) )
  690.  
  691. #define ubi_trInsert( Rp, Nn, Ip, On ) \
  692.         ubi_btInsert( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Nn), \
  693.                       (ubi_btItemPtr)(Ip), (ubi_btNodePtr *)(On) )
  694.  
  695. #define ubi_trRemove( Rp, Dn ) \
  696.         ubi_btRemove( (ubi_btRootPtr)(Rp), (ubi_btNodePtr)(Dn) )
  697.  
  698. #define ubi_trLocate( Rp, Ip, Op ) \
  699.         ubi_btLocate( (ubi_btRootPtr)(Rp), \
  700.                       (ubi_btItemPtr)(Ip), \
  701.                       (ubi_trCompOps)(Op) )
  702.  
  703. #define ubi_trFind( Rp, Ip ) \
  704.         ubi_btFind( (ubi_btRootPtr)(Rp), (ubi_btItemPtr)(Ip) )
  705.  
  706. #define ubi_trNext( P ) ubi_btNext( (ubi_btNodePtr)(P) )
  707.  
  708. #define ubi_trPrev( P ) ubi_btPrev( (ubi_btNodePtr)(P) )
  709.  
  710. #define ubi_trFirst( P ) ubi_btFirst( (ubi_btNodePtr)(P) )
  711.  
  712. #define ubi_trLast( P ) ubi_btLast( (ubi_btNodePtr)(P) )
  713.  
  714. #define ubi_trFirstOf( Rp, Ip, P ) \
  715.         ubi_btFirstOf( (ubi_btRootPtr)(Rp), \
  716.                        (ubi_btItemPtr)(Ip), \
  717.                        (ubi_btNodePtr)(P) )
  718.  
  719. #define ubi_trLastOf( Rp, Ip, P ) \
  720.         ubi_btLastOf( (ubi_btRootPtr)(Rp), \
  721.                       (ubi_btItemPtr)(Ip), \
  722.                       (ubi_btNodePtr)(P) )
  723.  
  724. #define ubi_trTraverse( Rp, En, Ud ) \
  725.         ubi_btTraverse((ubi_btRootPtr)(Rp), (ubi_btActionRtn)(En), (void *)(Ud))
  726.  
  727. #define ubi_trKillTree( Rp, Fn ) \
  728.         ubi_btKillTree( (ubi_btRootPtr)(Rp), (ubi_btKillNodeRtn)(Fn) )
  729.  
  730. #define ubi_trLeafNode( Nd ) \
  731.         ubi_btLeafNode( (ubi_btNodePtr)(Nd) )
  732.  
  733. #define ubi_trModuleID( s, l ) ubi_btModuleID( s, l )
  734.  
  735. /* ========================================================================== */
  736. #endif /* ubi_BinTree_H */
  737.